A.1 Proof of Lemma 1 The MSE can be computed as E null null ˆ x x null This proves that the estimate (4) is unbiased. A.3 Proof of Theorem 1 The MSE can be computed as E null null ˆ x x null A.5 Proof of Theorem 3 The MSE can be written as E null null ˆ x x null G, by the definition of G. 19 Now using our result in (70) and our inductive assumption we have, E null null null nullw For the purpose of this simulation, we first generate 5 all-(1) vectors and 5 all-(-1) vectors. This is corroborated by our experimental findings in Figure 1. Note that in all cases, data is partitioned equally among all nodes. Rand-k -Temporal significantly outperform other baselines in all settings .

See Section 4 for more details of prior work on exploiting temporal correlation.

We study the problem of communication-efficient distributed vector mean estimation, a commonly used subroutine in distributed optimization and Federated Learning (FL). Rand-$k$ sparsification is a commonly used technique to reduce communication cost, where each client sends $k < d$ of its coordinates to the server. However, Rand-$k$ is agnostic to any correlations, that might exist between clients in practical scenarios. The recently proposed Rand-$k$-Spatial estimator leverages the cross-client correlation information at the server to improve Rand-$k$'s performance. Yet, the performance of Rand-$k$-Spatial is suboptimal. We propose the Rand-Proj-Spatial estimator with a more flexible encoding-decoding procedure, which generalizes the encoding of Rand-$k$ by projecting the client vectors to a random $k$-dimensional subspace. We utilize Subsampled Randomized Hadamard Transform (SRHT) as the projection matrix and show that Rand-Proj-Spatial with SRHT outperforms Rand-$k$-Spatial, using the correlation information more efficiently. Furthermore, we propose an approach to incorporate varying degrees of correlation and suggest a practical variant of Rand-Proj-Spatial when the correlation information is not available to the server. Experiments on real-world distributed optimization tasks showcase the superior performance of Rand-Proj-Spatial compared to Rand-$k$-Spatial and other more sophisticated sparsification techniques.